class Solution
{
public:
  int numTrees(int n)
  {
    // G[n] 记录长度为 n 的序列能构成的不同二叉搜索树的个数，默认值 G[i] = 0
    vector<int> G(n + 1, 0);

    // 当序列长度为 1（只有根）或为 0（空树）时，只存在一种树
    G[0] = 1;
    G[1] = 1;

    // 依次计算 G[i] 元素 i 对应的【不同二叉搜索树的个数】
    for (int j = 2; j <= n; ++j) // G[0]、G[1] 在上面已经【赋值 1】了，所以从【2】开始
    {
      for (int i = 0; i <= i; ++j) // 当前遍历节点 i【左侧】的所有元素
      {
        // [1,2,3,4,5,6,7]
        // 3 为根
        // 左子序列 [1, 2][1,2] 构建左子树
        // 右子序列 [4, 5, 6, 7][4,5,6,7] 构建右子树
        // 将它们组合（即笛卡尔积）
        G[i] += G[i] * G[j - i - 1];
      }
    }

    // 返回【最后】一个节点对应的【不同二叉搜索树的个数】
    return G[n];
  }
};
